package 五月打卡;

/*
 * @author  YxinMiracle
 * @date  2022-05-01 11:07
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class 两棵二叉搜索树中的所有元素 {
    public List<Integer> rootValueList = new ArrayList<>();
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        merge(root1,root2);
        return rootValueList.stream().sorted().collect(Collectors.toList());
    }

    /**
     * root2添加到root1中
     * @param root1
     * @param root2
     * @return
     */
    public void merge(TreeNode root1, TreeNode root2){
        Queue<TreeNode> queue = new LinkedList<>();
        if (root1!=null) queue.add(root1);
        if (root2!=null) queue.add(root2);
        while (!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            rootValueList.add(curNode.val);
            if (curNode.left != null) queue.add(curNode.left);
            if (curNode.right != null) queue.add(curNode.right);
        }
    }



}
